# 53/100 图论-课程表(好题)
# leetcode第207题: https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/10
import json
import collections

from leetcode import test

"""
本题主要考察如何判断有向图中是否有环:
1. 判断一个有向图是否为一个有环的结构
2. 若图为一个弱连通图或者非连通图
prerequisites[i] = [ai, bi], 由于 0 <= ai, bi < numCourses 所以只要存在环路就一定不满足要求, 无需计算环路中有多少个节点.

本题是一个经典的「拓扑排序」问题.
给定一个包含 n 个节点的有向图 G, 我们给出它的节点编号的一种排列, 
如果满足：对于图 G 中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面. 那么称该排列是图 G 的「拓扑排序」. 
根据上述的定义，我们可以得出两个结论:
    1. 如果图 G 中存在环（即图 G 不是「有向无环图」），那么图 G 不存在拓扑排序。因为环中的节点不存在绝对的前后位置.
    2. 如果图 G 是有向无环图，那么它的拓扑排序可能不止一种。比如图中存在多个节点, 而没有一条边, 那么任意排序都可以成为拓扑排序.
"""


def canFinish(prerequisites: list[list[int]]) -> bool:
    """我的方法, 效率较低"""
    # 构建邻接矩阵表
    adj_list = {}
    for edge in prerequisites:
        if edge[1] not in adj_list:
            adj_list[edge[1]] = []
        adj_list[edge[1]].append(edge[0])

    def dfs(curr: int):
        """回溯法"""
        nonlocal visited, stack
        if curr in stack:
            return False
        if curr in visited:
            return True

        stack.add(curr)
        visited.add(curr)

        if adj_list.get(curr):
            for neighbor in adj_list[curr]:
                if not dfs(neighbor):
                    return False

        stack.remove(curr)  # 如果某个链路没有闭环, 则删除该节点
        return True

    for i in adj_list.keys():  # 考虑图为非连通图, 或者为弱连通图
        stack = set()  # 通过stack变量来判断某个链路是否形成了闭环
        visited = set()
        if not dfs(i):
            return False

    return True


def canFinish_opt(numCourses: int, prerequisites: list[list[int]]) -> bool:
    """
    参考拓扑排序的方法修改了我的方法, 发现主要的性能损耗为:
    1. 是否使用由普通的dict修改为defaultdict
    2. visited不需要每次都初始化, 且可以使用一个数组来进行表示

    defaultdict 和普通 dict 的区别在于, 当键不存在的时候就不会抛出KeyError异常, 而是会返回一个默认值:
    dd = defaultdict(int)
    dd_list = defaultdict(list)
    dd_set = defaultdict(set)
    dd_dict = defaultdict(dict)

    # 访问不存在的键
    print(dd['new_key'])       # 输出: 0
    print(dd_list['new_key'])  # 输出: []
    print(dd_set['new_key'])   # 输出: set()
    print(dd_dict['new_key'])  # 输出: {}

    """
    # 构建邻接矩阵表
    adj_list = collections.defaultdict(list)  # 由普通的dict修改为defaultdict
    visited = [False] * numCourses  # 修改了这里
    for edge in prerequisites:
        adj_list[edge[1]].append(edge[0])

    def dfs(curr: int):
        """回溯法"""
        nonlocal visited, stack
        if curr in stack:
            return False
        if visited[curr]:
            return True

        stack.add(curr)
        visited[curr] = True

        if adj_list.get(curr):
            for neighbor in adj_list[curr]:
                if not dfs(neighbor):
                    return False

        stack.remove(curr)  # 如果某个链路没有闭环, 则删除该节点
        return True

    for i in adj_list.keys():  # 考虑图为非连通图, 或者为弱连通图
        stack = set()  # 通过stack变量来判断某个链路是否形成了闭环
        if not dfs(i):
            return False

    return True


def canFinish_topological_sorting(numCourses: int, prerequisites: list[list[int]]) -> bool:
    """拓扑排序
    在搜索过程中将一个节点定义为3种状态:
    1. 未搜索(0): 还没有遍历到该节点
    2. 搜索中(1): 搜索过这个节点, 但是还没有回溯到该节点, 即该节点还没有入栈, 还有相邻的节点没有搜索完成
    3. 已完成(2): 我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求.
    根据上面的三种状态, 我们可以将搜索流程定义如下:
    1. 我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v:
        - 如果 v 为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u;
        - 如果 v 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的;
        - 如果 v 为「已完成」，那么说明 v 已经在栈中了，而 u 还不在栈中，因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及
          不用进行任何操作.
    2. 当 u 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」.
    """
    adj_list = collections.defaultdict(list)
    visited = [0] * numCourses
    is_acyclic = True  # is_acyclic 无环的, 非循环的
    result = []

    # 构建邻接表
    for edge in prerequisites:
        adj_list[edge[1]].append(edge[0])

    def dfs(curr: int):
        nonlocal is_acyclic
        visited[curr] = 1  # 访问中
        for neighbor in adj_list[curr]:
            if visited[neighbor] == 0:
                dfs(neighbor)
                if not is_acyclic:
                    return
            elif visited[neighbor] == 1:  # 有邻居节点也在访问中, 说明该链路是形成了闭环
                is_acyclic = False
                return
        visited[curr] = 2
        result.append(curr)

    for i in range(numCourses):
        if is_acyclic and not visited[i]:
            dfs(i)

    return is_acyclic


if __name__ == '__main__':
    prerequisites = [[1, 0]]
    prerequisites1 = [[1, 0], [0, 1]]
    prerequisites2 = [[1, 0], [2, 0], [3, 0], [3, 2], ]
    prerequisites3 = [[1, 0], [2, 0], [3, 0], [3, 2], [4, 3], [0, 4]]
    prerequisites4 = [[1, 0], [2, 1], [3, 2], ]
    with open("../data/i_graph3_lc207.data", "r") as file:
        readlines = file.read().strip()
        jo = json.loads(readlines)

    inp = [{"numCourses": 2, "prerequisites": prerequisites},
           {"numCourses": 2, "prerequisites": prerequisites1},
           {"numCourses": 4, "prerequisites": prerequisites2},
           {"numCourses": 5, "prerequisites": prerequisites3},
           {"numCourses": jo["numCourses"], "prerequisites": jo["prerequisites"]}, ]
    out = [True, False, True, False, True]

    test.test_function(canFinish, inp, out)
    test.test_function(canFinish_opt, inp, out)
    test.test_function(canFinish_topological_sorting, inp, out)
